package serchtree;
/**
 * 基于整型的
 * 普通的二分搜索树
 * @author yuisama
 * @date 2022/03/11 21:09
 **/
public class BST {
    private class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    private int size;
    private TreeNode root;

    public void add(int val) {
        root = add(root,val);
    }

    /**
     * 判断当前树中是否存在val
     * @param val
     * @return
     */
    public boolean contains(int val) {
        return contains(root,val);
    }

    /**
     * 判断当前以root为根的BST中是否包含了val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(TreeNode root, int val) {
        // 边界
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            // 找到了
            return true;
        }else if (val < root.val) {
            // 递归去左树中查找
            return contains(root.left,val);
        }else {
            // 递归去右树中查找
            return contains(root.right,val);
        }
    }

    /**
     * 向以root为根的BST中插入一个新的结点val
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val) {
        if (root == null) {
            // 创建新节点
            TreeNode newNode = new TreeNode(val);
            // 当前值就是根节点
            size ++;
            return newNode;
        }
        if (val < root.val) {
            // 左树中插入
            root.left = add(root.left,val);
        }
        if (val > root.val) {
            // 右树插入
            root.right = add(root.right,val);
        }
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 先序遍历以root为根的BST，将节点值存储在sb中
     * @param root
     * @param height
     * @param sb
     */
    private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        // 边界
        if (root == null) {
            sb.append(generatHeightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generatHeightStr(height)).append(root.val).append("\n");
        // 递归访问左子树
        generateBSTString(root.left,height + 1,sb);
        // 递归访问右子树
        generateBSTString(root.right,height + 1,sb);
    }

    /**
     * 按照当前所处的树的层次打印 --
     * 每多一层，就多两个--
     * @param height
     * @return
     */
    private String generatHeightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}